/*
 * avl.c
 *
 *  Created on: 31/05/2011
 *      Author: fernando
 */

#include "avl.h"
#include <stdlib.h>
#include <string.h>

void inicializa(No **raiz) {
	*raiz = NULL;
}

No *busca(char *x, No *raiz){
	while ((raiz != NULL) && (strcmp(raiz->word, x) != 0) ){
			if (strcmp(raiz->word, x) < 0) raiz = raiz->dir;
			else raiz = raiz->esq;
	}
	return raiz;
}

int insereAVL(char *word, Texto *texto, Linha *linha, No **p){
	int cresceu;

	if (*p == NULL) {
		*p = (No *) malloc(sizeof(No));
		(*p)->dir = (*p)->esq = NULL;
		(*p)->bal = 0;
		inicializaNoTexto(&((*p)->textos));
		strcpy((*p)->word, word);
		insereNoTexto(linha, texto, &((*p)->textos));
		cresceu = 1;
	}

	else if(strcmp((*p)->word, word) > 0) {
		cresceu = insereAVL(word, texto, linha, &(*p)->esq);
		if (cresceu) {
			switch((*p)->bal) {
			case 1:
				(*p)->bal = 0;
				cresceu = 0;
				break;
			case 0:
				(*p)->bal = -1;
				cresceu = 1;
				break;
			case -1:
				if ((*p)->esq->bal == -1) {
					rot_dir(p);
					(*p)->bal = (*p)->dir->bal = 0;
				}
				else {
					rot_esq(&(*p)->esq);
					rot_dir(p);
					if ((*p)->bal == -1) {
						(*p)->esq->bal = 0;
						(*p)->dir->bal = 1;
					}
					else {
						(*p)->dir->bal = 0;
						(*p)->esq->bal = -(*p)->bal;
					}
					(*p)->bal = 0;
				}
				cresceu = 0;
			}
		}
	}

	else if (strcmp((*p)->word, word) < 0) {
		cresceu = insereAVL(word, texto, linha, &(*p)->dir);
		if (cresceu) {
			switch((*p)->bal) {
			case -1:
				(*p)->bal = 0;
				cresceu = 0;
				break;
			case 0:
				(*p)->bal = 1;
				cresceu = 1;
				break;
			case 1:
				if ((*p)->dir->bal == 1) {
					rot_esq(p);
					(*p)->bal = (*p)->esq->bal = 0;
				}
				else {
					rot_dir(&(*p)->dir);
					rot_esq(p);
					if ((*p)->bal == -1) {
						(*p)->esq->bal = 0;
						(*p)->dir->bal = 1;
					}
					else {
						(*p)->dir->bal = 0;
						(*p)->esq->bal = -(*p)->bal;
					}
					(*p)->bal = 0;
				}
				cresceu = 0;
			}
		}
	}
	else {
		insereNoTexto(linha, texto, &((*p)->textos));
		cresceu = 0;
	}
	return cresceu;

}

void rot_dir(No **p){
	No *aux;
	aux = (*p)->esq;
	(*p)->esq = aux->dir;
	aux->dir = *p;
	*p = aux;
}

void rot_esq(No **p) {
	No *aux;
	aux = (*p)->dir;
	(*p)->dir = aux->esq;
	aux->esq = *p;
	*p = aux;
}
